package code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class Code17 {

	public void dfs(int step,String digits,Map<Integer,List> map,List<Character> list,List<String> res){
		if(step==digits.length()){
			StringBuilder sb=new StringBuilder();
			for(int i=0;i<list.size();i++){
				sb.append(list.get(i));
			}
			res.add(sb.toString());
			return ;
		}
		int dd=digits.charAt(step)-'0';
		List<Character> table=map.get(dd);
		for(int i=0;i<table.size();i++){
			list.add(table.get(i));
			dfs(step+1,digits,map,list,res);
			list.remove(list.size()-1);
		}
	}
    public List<String> letterCombinations(String digits) {
    	List<String> result=new ArrayList<String>();
    	Map<Integer,List> map=new HashMap<Integer,List>();
    	char cc='a';
    	for(int i=2;i<=9;i++){
    		List<Character> list=new ArrayList<Character>();
    		map.put(i, list);
    		list.add((char)(cc));
    		cc++;
    		list.add((char)(cc));
    		cc++;
    		list.add((char)(cc));
    		if(i==7 || i==9){
    			cc++;
    			list.add((char)(cc));
    		}
    		cc++;
    	}
    	if(digits.length()==0)
    		return result;
    	dfs(0,digits,map,new ArrayList(),result);
        return result;
    }
    public static void main(String[] args){
    	new Code17().letterCombinations("23");
    }
}
